// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

// 返回滑动窗口中的最大值。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/sliding-window-maximum
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
using namespace std;

// 模拟
// 59/61超时（递减）

class Solution {
public:
    int findmax(vector<int>& nums,int begin,int end){
        int imax =*max_element(nums.begin()+begin,nums.begin()+end);
        return imax;
    }

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len =nums.size();
        if(len<2){
            return nums;
        }
        vector<int> res;
        // 找到最大
        int imax = findmax(nums,0,k);
        // 模拟滑动窗口
        res.push_back(imax);
        for(int i=1;i<=len-k;i++){
            if(nums[i+k-1]>=imax){
                imax=nums[i+k-1];
            }
            else if(nums[i-1]==imax){
                imax=findmax(nums,i,i+k);
            }
            res.push_back(imax);
        }
        return res;

    }
};